#ifndef ARVOREV_H_
#define ARVOREV_H_
#include <cstdlib>
#include <iostream>
#include <iomanip>
#include <exception>

using namespace std;


template<class TCHV, class TDADO>
struct NoV
{
	TCHV Chave;
	vector<TDADO> Valor;
	NoV<TCHV,TDADO> *esq, *dir;
	NoV()
	{
		esq = dir = NULL;
	}
	NoV(TCHV c, TDADO v, NoV<TCHV, TDADO> *e = NULL, NoV<TCHV, TDADO> *d = NULL)
	{
		Chave = c;
		Valor.push_back(v);
		esq = e;
		dir = d;
	}

};

template<class TCHV, class TDADO>
class ArvoreV
{
private:
	NoV<TCHV, TDADO> *raiz;
public:
	ArvoreV()
	{
		raiz = NULL;
	}

	virtual ~ArvoreV()
	{
		NoV<TCHV,TDADO> *tmp = raiz;
		while(tmp != NULL)
		{
			tmp = Remover(tmp->Chave, tmp);
		}
	}

	void Limpa()
	{
		NoV<TCHV,TDADO> *tmp = raiz;
		while(tmp != NULL)
		{
			tmp = Remover(tmp->Chave, tmp);
		}
		raiz = new NoV<TCHV, TDADO>();
	}

	bool Vazia()
	{
		return raiz == NULL;
	}
private:
	NoV<TCHV, TDADO> *Insere(TCHV chv, TDADO dado, NoV<TCHV,TDADO> *sub)
	{
	  if ( sub == NULL ) // Encontrou posi��o
	  {
	    sub = new NoV<TCHV, TDADO>( chv, dado );
	  }
	  else
	  {
		if ( chv.compare(sub->Chave) < 0 )
	    {
	      sub->esq = Insere( chv, dado, sub->esq );
	    }
	    else
	    {
	      if ( chv.compare(sub->Chave) > 0 )
	      {
	        sub->dir = Insere( chv, dado, sub->dir );
	      }
	      else
	      {
	    	sub->Valor.push_back(dado);
	        return sub; // N� encontrado!
	      }
	    }
	  }
	  return sub;
	}


	NoV<TCHV,TDADO> *LocalizarMin( NoV<TCHV,TDADO> *subarv )
	{
	  if ( subarv->esq != NULL ) subarv = LocalizarMin( subarv->esq );
	  return subarv;

	}

	NoV<TCHV,TDADO> * Localizar( TCHV chv, NoV<TCHV,TDADO> * subarv )
	{

	  if ( subarv == NULL ) {
		  return NULL;
	  }
	  else
	  {
	    if ( chv.compare(subarv->Chave) < 0 ) {
	      return Localizar( chv, subarv->esq );
	    }
	    else
	    {
	      if ( chv.compare(subarv->Chave) > 0 ) {
	        return Localizar( chv, subarv->dir );
	      }
	      else
	        return subarv; // No Encontrado
	    }
	  }
	}

	NoV<TCHV,TDADO> * Remover( TCHV chave, NoV<TCHV,TDADO> * subarv )
	{
	  NoV<TCHV,TDADO> * tmp, * filho;
	  if ( subarv == NULL )
	  {
	    return NULL; // N� n�o encontrado!
	  }
	  else
	  {
	    if ( chave < subarv->Chave )
	    {
	      subarv->esq = Remover( chave, subarv->esq );
	    }
	    else
	    {
	      if ( chave > subarv->Chave )
	      {
	        subarv->dir = Remover( chave, subarv->dir );
	      }
	      else
	      {
	        if ( subarv->esq && subarv->dir )
	        {
	          tmp = LocalizarMin( subarv->dir );
	          subarv->Chave = tmp->Chave;
	          subarv->dir = Remover( subarv->Chave, subarv->dir );
	        }
	        else
	        {
	          tmp = subarv;
	          if ( subarv->esq == NULL ) filho = subarv->dir;
	          if ( subarv->dir == NULL ) filho = subarv->esq;
	          delete tmp;
	          return filho;
	        }
	      }
	    }
	  }
	  return subarv;
	}

	void Imprime( NoV<TCHV,TDADO> *subarv, int nv )
	{
	  if ( subarv == NULL ) return;
	  Imprime( subarv->dir, nv + 1 );
	  cout << setw(nv*5) << " " << subarv->Chave << endl;
	  Imprime( subarv->esq, nv + 1 );
	}

	int Altura( NoV<TCHV,TDADO> * subarv )
	{
	  int ae, ad;
	  if ( subarv == NULL ) return 0;
	  if ( subarv->esq == NULL && subarv->dir == NULL ) return 1;
	  ae = Altura( subarv->esq );
	  ad = Altura( subarv->dir );
	  if ( ae > ad )
		return ae + 1;
	  else
	    return ad + 1;
	}

public:

	void Insere(TCHV chave, TDADO dado)
	{
		raiz = Insere(chave, dado, raiz);
	}

	void Remove(TCHV chave)
	{
		raiz = Remover(chave, raiz);
	}

	vector<TDADO> Seleciona(TCHV chave)
	{
		NoV<TCHV,TDADO> *tmp = Localizar(chave, raiz);
		if(tmp == NULL) throw exception();
		return tmp->Valor;
	}

	void Imprime()
	{
		Imprime(raiz,1);
	}

	void Altura()
	{
		return Altura(raiz);
	}

};

#endif /*ARVOREV_H_*/
